<!doctype html><html lang=cn-zh><head><meta charset=UTF-8><meta name=viewport content="width=device-width,initial-scale=1"><meta http-equiv=X-UA-Compatible content="IE=edge"><style type=text/css>body{font-family:monospace}</style><title>《算法图解》读书笔记7-狄克斯特拉算法</title>
<meta name=description content="A blog maintained by Vimiix."><link rel=stylesheet href=/css/style.css><script>var _hmt=_hmt||[];(function(){var e,t=document.createElement("script");t.src="https://hm.baidu.com/hm.js?7c24231917964240bae97e813810620c",e=document.getElementsByTagName("script")[0],e.parentNode.insertBefore(t,e)})()</script></head><body><header>====================<br>== Hi, I'm Vimiix ==<br>====================<div style=float:right;color:gray;font-size:x-large>Get hands dirty.</div><br><p><nav><a href=https://www.vimiix.com/><b>首页</b></a>.
<a href=/posts/><b>文章列表</b></a>.
<a href=/projects/><b>开源项目</b></a>.
<a href=/tags/><b>标签</b></a>.
<a href=/friends/><b>友链</b></a>.
<a href=/about/><b>关于我</b></a>.
<a href=/index.xml><b>RSS</b></a>.</nav></p></header><main><article><h1>《算法图解》读书笔记7-狄克斯特拉算法</h1><b><time>2018.07.16 22:20</time></b>
<a href=/tags/algorithm>algorithm</a>
<a href=/tags/python>Python</a>
<a href=/tags/dijkstra>Dijkstra</a><div><h2 id=概念>概念</h2><blockquote><p>狄克斯特拉算法是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题 (该算法不能处理包含负边的图)。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。</p></blockquote><h2 id=python-实现收藏>Python 实现（收藏）</h2><div class=highlight><pre tabindex=0 style=color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4><code class=language-python data-lang=python><span style=display:flex><span><span style=color:#75715e>#coding:utf8</span>
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span>graph <span style=color:#f92672>=</span> {
</span></span><span style=display:flex><span><span style=color:#e6db74>&#39;N1&#39;</span>: {<span style=color:#e6db74>&#39;N2&#39;</span>: <span style=color:#ae81ff>1</span>},
</span></span><span style=display:flex><span><span style=color:#e6db74>&#39;N12&#39;</span>:{<span style=color:#e6db74>&#39;N13&#39;</span>:<span style=color:#ae81ff>1</span>},
</span></span><span style=display:flex><span><span style=color:#e6db74>&#39;N2&#39;</span>: {<span style=color:#e6db74>&#39;N4&#39;</span>: <span style=color:#ae81ff>1</span>, <span style=color:#e6db74>&#39;N13&#39;</span>:<span style=color:#ae81ff>1</span>},
</span></span><span style=display:flex><span><span style=color:#e6db74>&#39;N4&#39;</span>: {<span style=color:#e6db74>&#39;N5&#39;</span>: <span style=color:#ae81ff>1</span>, <span style=color:#e6db74>&#39;N12&#39;</span>: <span style=color:#ae81ff>1</span>},
</span></span><span style=display:flex><span><span style=color:#e6db74>&#39;N5&#39;</span>: {<span style=color:#e6db74>&#39;N6&#39;</span>: <span style=color:#ae81ff>1</span>},
</span></span><span style=display:flex><span><span style=color:#e6db74>&#39;N6&#39;</span>: {<span style=color:#e6db74>&#39;N7&#39;</span>: <span style=color:#ae81ff>1</span>},
</span></span><span style=display:flex><span><span style=color:#e6db74>&#39;N7&#39;</span>: {<span style=color:#e6db74>&#39;N8&#39;</span>: <span style=color:#ae81ff>1</span>},
</span></span><span style=display:flex><span><span style=color:#e6db74>&#39;N8&#39;</span>: {<span style=color:#e6db74>&#39;N9&#39;</span>:<span style=color:#ae81ff>1</span>},
</span></span><span style=display:flex><span><span style=color:#e6db74>&#39;N9&#39;</span>: {<span style=color:#e6db74>&#39;N10&#39;</span>: <span style=color:#ae81ff>1</span>, <span style=color:#e6db74>&#39;N11&#39;</span>: <span style=color:#ae81ff>1</span>, <span style=color:#e6db74>&#39;N12&#39;</span>:<span style=color:#ae81ff>1</span>},
</span></span><span style=display:flex><span><span style=color:#e6db74>&#39;N10&#39;</span>: {<span style=color:#e6db74>&#39;N11&#39;</span>:<span style=color:#ae81ff>1</span>},
</span></span><span style=display:flex><span><span style=color:#e6db74>&#39;N11&#39;</span>: {<span style=color:#e6db74>&#39;N12&#39;</span>:<span style=color:#ae81ff>1</span>},
</span></span><span style=display:flex><span><span style=color:#e6db74>&#39;N13&#39;</span>:{<span style=color:#e6db74>&#39;N12&#39;</span>:<span style=color:#ae81ff>1</span>}
</span></span><span style=display:flex><span>}
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span><span style=color:#75715e># Dijkstra&#39;s algorithm for shortest paths</span>
</span></span><span style=display:flex><span><span style=color:#75715e># David Eppstein, UC Irvine, 4 April 2002</span>
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span><span style=color:#75715e># http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/117228</span>
</span></span><span style=display:flex><span><span style=color:#f92672>from</span> priodict <span style=color:#f92672>import</span> priorityDictionary
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span><span style=color:#66d9ef>def</span> <span style=color:#a6e22e>Dijkstra</span>(G,start,end<span style=color:#f92672>=</span><span style=color:#66d9ef>None</span>):
</span></span><span style=display:flex><span>    <span style=color:#e6db74>&#34;&#34;&#34;
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    Find shortest paths from the start vertex to all
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    vertices nearer than or equal to the end.
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    The input graph G is assumed to have the following
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    representation: A vertex can be any object that can
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    be used as an index into a dictionary.  G is a
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    dictionary, indexed by vertices.  For any vertex v,
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    G[v] is itself a dictionary, indexed by the neighbors
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    of v.  For any edge v-&gt;w, G[v][w] is the length of
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    the edge.  This is related to the representation in
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    &lt;http://www.python.org/doc/essays/graphs.html&gt;
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    where Guido van Rossum suggests representing graphs
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    as dictionaries mapping vertices to lists of neighbors,
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    however dictionaries of edges have many advantages
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    over lists: they can store extra information (here,
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    the lengths), they support fast existence tests,
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    and they allow easy modification of the graph by edge
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    insertion and removal.  Such modifications are not
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    needed here but are important in other graph algorithms.
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    Since dictionaries obey iterator protocol, a graph
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    represented as described here could be handed without
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    modification to an algorithm using Guido&#39;s representation.
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    Of course, G and G[v] need not be Python dict objects;
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    they can be any other object that obeys dict protocol,
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    for instance a wrapper in which vertices are URLs
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    and a call to G[v] loads the web page and finds its links.
</span></span></span><span style=display:flex><span><span style=color:#e6db74>
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    The output is a pair (D,P) where D[v] is the distance
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    from start to v and P[v] is the predecessor of v along
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    the shortest path from s to v.
</span></span></span><span style=display:flex><span><span style=color:#e6db74>
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    Dijkstra&#39;s algorithm is only guaranteed to work correctly
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    when all edge lengths are positive. This code does not
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    verify this property for all edges (only the edges seen
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    before the end vertex is reached), but will correctly
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    compute shortest paths even for some graphs with negative
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    edges, and will raise an exception if it discovers that
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    a negative edge has caused it to make a mistake.
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    &#34;&#34;&#34;</span>
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span>    D <span style=color:#f92672>=</span> {}  <span style=color:#75715e># dictionary of final distances</span>
</span></span><span style=display:flex><span>    P <span style=color:#f92672>=</span> {}  <span style=color:#75715e># dictionary of predecessors</span>
</span></span><span style=display:flex><span>    Q <span style=color:#f92672>=</span> priorityDictionary()   <span style=color:#75715e># est.dist. of non-final vert.</span>
</span></span><span style=display:flex><span>    Q[start] <span style=color:#f92672>=</span> <span style=color:#ae81ff>0</span>
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span>    <span style=color:#66d9ef>for</span> v <span style=color:#f92672>in</span> Q:
</span></span><span style=display:flex><span>        D[v] <span style=color:#f92672>=</span> Q[v]
</span></span><span style=display:flex><span>        <span style=color:#66d9ef>if</span> v <span style=color:#f92672>==</span> end: <span style=color:#66d9ef>break</span>
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span>        <span style=color:#66d9ef>for</span> w <span style=color:#f92672>in</span> G[v]:
</span></span><span style=display:flex><span>            vwLength <span style=color:#f92672>=</span> D[v] <span style=color:#f92672>+</span> G[v][w]
</span></span><span style=display:flex><span>            <span style=color:#66d9ef>if</span> w <span style=color:#f92672>in</span> D:
</span></span><span style=display:flex><span>                <span style=color:#66d9ef>if</span> vwLength <span style=color:#f92672>&lt;</span> D[w]:
</span></span><span style=display:flex><span>                    <span style=color:#66d9ef>raise</span> <span style=color:#a6e22e>ValueError</span>, \
</span></span><span style=display:flex><span>  <span style=color:#e6db74>&#34;Dijkstra: found better path to already-final vertex&#34;</span>
</span></span><span style=display:flex><span>            <span style=color:#66d9ef>elif</span> w <span style=color:#f92672>not</span> <span style=color:#f92672>in</span> Q <span style=color:#f92672>or</span> vwLength <span style=color:#f92672>&lt;</span> Q[w]:
</span></span><span style=display:flex><span>                Q[w] <span style=color:#f92672>=</span> vwLength
</span></span><span style=display:flex><span>                P[w] <span style=color:#f92672>=</span> v
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span>    <span style=color:#66d9ef>return</span> (D,P)
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span><span style=color:#66d9ef>def</span> <span style=color:#a6e22e>shortestPath</span>(G,start,end):
</span></span><span style=display:flex><span>    <span style=color:#e6db74>&#34;&#34;&#34;
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    Find a single shortest path from the given start vertex
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    to the given end vertex.
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    The input has the same conventions as Dijkstra().
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    The output is a list of the vertices in order along
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    the shortest path.
</span></span></span><span style=display:flex><span><span style=color:#e6db74>    &#34;&#34;&#34;</span>
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span>    D,P <span style=color:#f92672>=</span> Dijkstra(G,start,end)
</span></span><span style=display:flex><span>    Path <span style=color:#f92672>=</span> []
</span></span><span style=display:flex><span>    <span style=color:#66d9ef>while</span> <span style=color:#ae81ff>1</span>:
</span></span><span style=display:flex><span>        Path<span style=color:#f92672>.</span>append(end)
</span></span><span style=display:flex><span>        <span style=color:#66d9ef>if</span> end <span style=color:#f92672>==</span> start: <span style=color:#66d9ef>break</span>
</span></span><span style=display:flex><span>        end <span style=color:#f92672>=</span> P[end]
</span></span><span style=display:flex><span>    Path<span style=color:#f92672>.</span>reverse()
</span></span><span style=display:flex><span>    <span style=color:#66d9ef>return</span> Path
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span>print shortestPath(graph, <span style=color:#e6db74>&#39;N1&#39;</span>,<span style=color:#e6db74>&#39;N13&#39;</span>)
</span></span><span style=display:flex><span>print shortestPath(graph, <span style=color:#e6db74>&#39;N1&#39;</span>,<span style=color:#e6db74>&#39;N12&#39;</span>)
</span></span></code></pre></div><h3 id=priodictpy>priodict.py</h3><div class=highlight><pre tabindex=0 style=color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4><code class=language-python data-lang=python><span style=display:flex><span><span style=color:#75715e># Priority dictionary using binary heaps</span>
</span></span><span style=display:flex><span><span style=color:#75715e># David Eppstein, UC Irvine, 8 Mar 2002</span>
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span><span style=color:#75715e># Implements a data structure that acts almost like a dictionary, with two modifications:</span>
</span></span><span style=display:flex><span><span style=color:#75715e># (1) D.smallest() returns the value x minimizing D[x].  For this to work correctly,</span>
</span></span><span style=display:flex><span><span style=color:#75715e>#        all values D[x] stored in the dictionary must be comparable.</span>
</span></span><span style=display:flex><span><span style=color:#75715e># (2) iterating &#34;for x in D&#34; finds and removes the items from D in sorted order.</span>
</span></span><span style=display:flex><span><span style=color:#75715e>#        Each item is not removed until the next item is requested, so D[x] will still</span>
</span></span><span style=display:flex><span><span style=color:#75715e>#        return a useful value until the next iteration of the for-loop.</span>
</span></span><span style=display:flex><span><span style=color:#75715e># Each operation takes logarithmic amortized time.</span>
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span><span style=color:#f92672>from</span> __future__ <span style=color:#f92672>import</span> generators
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span><span style=color:#66d9ef>class</span> <span style=color:#a6e22e>priorityDictionary</span>(dict):
</span></span><span style=display:flex><span>    <span style=color:#66d9ef>def</span> __init__(self):
</span></span><span style=display:flex><span>        <span style=color:#e6db74>&#39;&#39;&#39;Initialize priorityDictionary by creating binary heap of pairs (value,key).
</span></span></span><span style=display:flex><span><span style=color:#e6db74>Note that changing or removing a dict entry will not remove the old pair from the heap
</span></span></span><span style=display:flex><span><span style=color:#e6db74>until it is found by smallest() or until the heap is rebuilt.&#39;&#39;&#39;</span>
</span></span><span style=display:flex><span>        self<span style=color:#f92672>.</span>__heap <span style=color:#f92672>=</span> []
</span></span><span style=display:flex><span>        dict<span style=color:#f92672>.</span>__init__(self)
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span>    <span style=color:#66d9ef>def</span> <span style=color:#a6e22e>smallest</span>(self):
</span></span><span style=display:flex><span>        <span style=color:#e6db74>&#39;&#39;&#39;Find smallest item after removing deleted items from front of heap.&#39;&#39;&#39;</span>
</span></span><span style=display:flex><span>        <span style=color:#66d9ef>if</span> len(self) <span style=color:#f92672>==</span> <span style=color:#ae81ff>0</span>:
</span></span><span style=display:flex><span>            <span style=color:#66d9ef>raise</span> <span style=color:#a6e22e>IndexError</span>, <span style=color:#e6db74>&#34;smallest of empty priorityDictionary&#34;</span>
</span></span><span style=display:flex><span>        heap <span style=color:#f92672>=</span> self<span style=color:#f92672>.</span>__heap
</span></span><span style=display:flex><span>        <span style=color:#66d9ef>while</span> heap[<span style=color:#ae81ff>0</span>][<span style=color:#ae81ff>1</span>] <span style=color:#f92672>not</span> <span style=color:#f92672>in</span> self <span style=color:#f92672>or</span> self[heap[<span style=color:#ae81ff>0</span>][<span style=color:#ae81ff>1</span>]] <span style=color:#f92672>!=</span> heap[<span style=color:#ae81ff>0</span>][<span style=color:#ae81ff>0</span>]:
</span></span><span style=display:flex><span>            lastItem <span style=color:#f92672>=</span> heap<span style=color:#f92672>.</span>pop()
</span></span><span style=display:flex><span>            insertionPoint <span style=color:#f92672>=</span> <span style=color:#ae81ff>0</span>
</span></span><span style=display:flex><span>            <span style=color:#66d9ef>while</span> <span style=color:#ae81ff>1</span>:
</span></span><span style=display:flex><span>                smallChild <span style=color:#f92672>=</span> <span style=color:#ae81ff>2</span><span style=color:#f92672>*</span>insertionPoint<span style=color:#f92672>+</span><span style=color:#ae81ff>1</span>
</span></span><span style=display:flex><span>                <span style=color:#66d9ef>if</span> smallChild<span style=color:#f92672>+</span><span style=color:#ae81ff>1</span> <span style=color:#f92672>&lt;</span> len(heap) <span style=color:#f92672>and</span> heap[smallChild] <span style=color:#f92672>&gt;</span> heap[smallChild<span style=color:#f92672>+</span><span style=color:#ae81ff>1</span>] :
</span></span><span style=display:flex><span>                    smallChild <span style=color:#f92672>+=</span> <span style=color:#ae81ff>1</span>
</span></span><span style=display:flex><span>                <span style=color:#66d9ef>if</span> smallChild <span style=color:#f92672>&gt;=</span> len(heap) <span style=color:#f92672>or</span> lastItem <span style=color:#f92672>&lt;=</span> heap[smallChild]:
</span></span><span style=display:flex><span>                    heap[insertionPoint] <span style=color:#f92672>=</span> lastItem
</span></span><span style=display:flex><span>                    <span style=color:#66d9ef>break</span>
</span></span><span style=display:flex><span>                heap[insertionPoint] <span style=color:#f92672>=</span> heap[smallChild]
</span></span><span style=display:flex><span>                insertionPoint <span style=color:#f92672>=</span> smallChild
</span></span><span style=display:flex><span>        <span style=color:#66d9ef>return</span> heap[<span style=color:#ae81ff>0</span>][<span style=color:#ae81ff>1</span>]
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span>    <span style=color:#66d9ef>def</span> __iter__(self):
</span></span><span style=display:flex><span>        <span style=color:#e6db74>&#39;&#39;&#39;Create destructive sorted iterator of priorityDictionary.&#39;&#39;&#39;</span>
</span></span><span style=display:flex><span>        <span style=color:#66d9ef>def</span> <span style=color:#a6e22e>iterfn</span>():
</span></span><span style=display:flex><span>            <span style=color:#66d9ef>while</span> len(self) <span style=color:#f92672>&gt;</span> <span style=color:#ae81ff>0</span>:
</span></span><span style=display:flex><span>                x <span style=color:#f92672>=</span> self<span style=color:#f92672>.</span>smallest()
</span></span><span style=display:flex><span>                <span style=color:#66d9ef>yield</span> x
</span></span><span style=display:flex><span>                <span style=color:#66d9ef>del</span> self[x]
</span></span><span style=display:flex><span>        <span style=color:#66d9ef>return</span> iterfn()
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span>    <span style=color:#66d9ef>def</span> __setitem__(self,key,val):
</span></span><span style=display:flex><span>        <span style=color:#e6db74>&#39;&#39;&#39;Change value stored in dictionary and add corresponding pair to heap.
</span></span></span><span style=display:flex><span><span style=color:#e6db74>Rebuilds the heap if the number of deleted items gets large, to avoid memory leakage.&#39;&#39;&#39;</span>
</span></span><span style=display:flex><span>        dict<span style=color:#f92672>.</span>__setitem__(self,key,val)
</span></span><span style=display:flex><span>        heap <span style=color:#f92672>=</span> self<span style=color:#f92672>.</span>__heap
</span></span><span style=display:flex><span>        <span style=color:#66d9ef>if</span> len(heap) <span style=color:#f92672>&gt;</span> <span style=color:#ae81ff>2</span> <span style=color:#f92672>*</span> len(self):
</span></span><span style=display:flex><span>            self<span style=color:#f92672>.</span>__heap <span style=color:#f92672>=</span> [(v,k) <span style=color:#66d9ef>for</span> k,v <span style=color:#f92672>in</span> self<span style=color:#f92672>.</span>iteritems()]
</span></span><span style=display:flex><span>            self<span style=color:#f92672>.</span>__heap<span style=color:#f92672>.</span>sort()  <span style=color:#75715e># builtin sort probably faster than O(n)-time heapify</span>
</span></span><span style=display:flex><span>        <span style=color:#66d9ef>else</span>:
</span></span><span style=display:flex><span>            newPair <span style=color:#f92672>=</span> (val,key)
</span></span><span style=display:flex><span>            insertionPoint <span style=color:#f92672>=</span> len(heap)
</span></span><span style=display:flex><span>            heap<span style=color:#f92672>.</span>append(<span style=color:#66d9ef>None</span>)
</span></span><span style=display:flex><span>            <span style=color:#66d9ef>while</span> insertionPoint <span style=color:#f92672>&gt;</span> <span style=color:#ae81ff>0</span> <span style=color:#f92672>and</span> newPair <span style=color:#f92672>&lt;</span> heap[(insertionPoint<span style=color:#f92672>-</span><span style=color:#ae81ff>1</span>)<span style=color:#f92672>//</span><span style=color:#ae81ff>2</span>]:
</span></span><span style=display:flex><span>                heap[insertionPoint] <span style=color:#f92672>=</span> heap[(insertionPoint<span style=color:#f92672>-</span><span style=color:#ae81ff>1</span>)<span style=color:#f92672>//</span><span style=color:#ae81ff>2</span>]
</span></span><span style=display:flex><span>                insertionPoint <span style=color:#f92672>=</span> (insertionPoint<span style=color:#f92672>-</span><span style=color:#ae81ff>1</span>)<span style=color:#f92672>//</span><span style=color:#ae81ff>2</span>
</span></span><span style=display:flex><span>            heap[insertionPoint] <span style=color:#f92672>=</span> newPair
</span></span><span style=display:flex><span>
</span></span><span style=display:flex><span>    <span style=color:#66d9ef>def</span> <span style=color:#a6e22e>setdefault</span>(self,key,val):
</span></span><span style=display:flex><span>        <span style=color:#e6db74>&#39;&#39;&#39;Reimplement setdefault to pass through our customized __setitem__.&#39;&#39;&#39;</span>
</span></span><span style=display:flex><span>        <span style=color:#66d9ef>if</span> key <span style=color:#f92672>not</span> <span style=color:#f92672>in</span> self:
</span></span><span style=display:flex><span>            self[key] <span style=color:#f92672>=</span> val
</span></span><span style=display:flex><span>        <span style=color:#66d9ef>return</span> self[key]
</span></span></code></pre></div><h2 id=gist-地址>gist 地址：</h2><p><a href=https://gist.github.com/theonewolf/6175427>https://gist.github.com/theonewolf/6175427</a></p></div></article></main><aside><div><div><h3>LATEST POSTS</h3></div><div><ul><li><a href=/posts/2025-10-16-kubernetes-apiserver-authorization-mechanism/>Kubernetes APIServer 鉴权机制</a></li><li><a href=/posts/2025-09-30-kubernetes-apiserver-authentication-mechanism/>Kubernetes APIServer 认证机制</a></li><li><a href=/posts/2024-12-16-deploy-kubernetes-by-kubeadm/>使用 kubeadm 搭建 kubernetes 集群</a></li><li><a href=/posts/2024-09-20-how-to-code-review/>如何做code review</a></li><li><a href=/posts/2024-08-12-weakref-in-python/>Python中的弱引用</a></li></ul></div></div></aside><footer><p>Social Links:
<a href=https://github.com/vimiix><b>Github</b></a>.
<a href=https://www.douban.com/people/vimiix/><b>Douban</b></a>.
<a href=mailto:i@vimiix.com><b>Email</b></a>.<br><hr>&copy; 2017-2025
Vimiix Yao; All rights reserved.
<a href=https://beian.miit.gov.cn/>京ICP备19015214号-1</a></p><script src=https://l2dwidget.js.org/lib/L2Dwidget.min.js></script><script>L2Dwidget.init({model:{jsonPath:"https://unpkg.com/live2d-widget-model-tororo@1.0.5/assets/tororo.model.json"}})</script></footer></body></html>